package com.lx.algorithm.recursion.class18;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-18 12:31:13
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-18     张李鑫                     1.0         1.0 Version
 */
public class RobotWalk {
    /**
     * 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
     * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
     * 如果机器人来到1位置，那么下一步只能往右来到2位置；
     * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
     * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
     * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
     * 给定四个参数 N、M、K、P，返回方法数。
     */

    /**
     * @param k 步数
     * @param p 到达的位置
     * @param n 位置的个数
     * @param m 开始的位置
     * @return
     */
    public static int walk(int k, int p, int n, int m) {
        return process(k, p, n, m);
    }

    private static int process(int k, int p, int n, int m) {
        //步数走完了 如果m==p 说明有一种到达的路径
        if (k == 0) {
            return m == p ? 1 : 0;
        }

        if (m == 1) {
            return process(k - 1, p, n, 2);
        }

        if (m == n) {
            return process(k - 1, p, n, n - 1);
        }

        return process(k - 1, p, n, m - 1) + process(k - 1, p, n, m + 1);
    }


    public static int dp(int k, int p, int n, int m) {
        int[][] dp = new int[k + 1][n + 1];

        dp[0][p] = 1;

        for (int i = 1; i < dp.length; i++) {
            dp[i][1] = dp[i - 1][2];
            dp[i][n] = dp[i - 1][n - 1];
            for (int j = 2; j < dp[i].length-1; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
        }

        return dp[k][m];
    }

    public static void main(String[] args) {
        System.out.println(walk(16, 4, 5, 2));
        System.out.println(dp(16, 4, 5, 2));
    }
}
